package com.samxcode.leetcode;

import java.util.LinkedList;
import java.util.List;


/**
 * Given a digit string, return all possible letter combinations that the number could represent. A
 * mapping of digit to letters (just like on the telephone buttons) is given below.
 * 
 * Solution:
 * Similar to BFS
 * 
 * @author Sam
 *
 */
public class LetterCombiantions {
    
    public static void main(String[] args) {
        System.out.println(letterCombinations("2456"));
    }

    private static final char[][] LETTERS = { { 'a', 'b', 'c' }, { 'd', 'e', 'f' },
                                             { 'g', 'h', 'i' }, { 'j', 'k', 'l' },
                                             { 'm', 'n', 'o' }, { 'p', 'q', 'r', 's' },
                                             { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' } };


    public static List<String> letterCombinations(String digits) {
        LinkedList<String> queue = new LinkedList<String>();
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            for (int j = queue.size(); j > 0; j--) {
                String temp = queue.removeFirst();
                for (char c : LETTERS[digits.charAt(i) - '2']) {
                    queue.addLast(temp + c);
                }
            }
        }
        return queue;
    }
}
